// json parser

use std::{collections::BTreeSet, sync::atomic::{AtomicUsize, Ordering}};

#[derive(Debug, PartialEq)]
enum Data {
    Array(Vec<Data>),
    Object(Vec<(String, Data)>),
    String(String),
}

enum ParseMode {
    Array,
    Object,
    String,
}

impl Data {
    fn parse_skip_whitespace(json: &[char], pointer: &mut AtomicUsize) {
        while let Some(c) = json.get(pointer.load(Ordering::SeqCst)) {
            if !c.is_whitespace() {
                break;
            }
            pointer.fetch_add(1, Ordering::SeqCst);
        }
    }
    fn from_json_intern(json: &[char], pointer: &mut AtomicUsize, mode: ParseMode) -> Data {
        match mode {
            ParseMode::Array => {
                pointer.fetch_add(1, Ordering::SeqCst);
                Self::parse_skip_whitespace(json, pointer);
                let mut array = vec![];
                while let Some(c) = json.get(pointer.load(Ordering::SeqCst)) {
                    array.push(match *c {
                        '[' => Self::from_json_intern(json, pointer, ParseMode::Array),
                        '{' => Self::from_json_intern(json, pointer, ParseMode::Object),
                        '"' => Self::from_json_intern(json, pointer, ParseMode::String),
                        ']' => {
                            pointer.fetch_add(1, Ordering::SeqCst);
                            break;
                        }
                        _ => panic!("Invalid character in array: {}: {}", c, pointer.load(Ordering::SeqCst)),
                    });
                    Self::parse_skip_whitespace(json, pointer);
                    if let Some(c) = json.get(pointer.load(Ordering::SeqCst)) {
                        match *c {
                            ',' => {
                                pointer.fetch_add(1, Ordering::SeqCst);
                                Self::parse_skip_whitespace(json, pointer);
                            }
                            ']' => {
                                pointer.fetch_add(1, Ordering::SeqCst);
                                break;
                            }
                            _ => panic!("Invalid character in array: {}: {}", c, pointer.load(Ordering::SeqCst)),
                        }
                    } else {
                        panic!("Unexpected end of input in array");
                    }
                }
                Data::Array(array)
            },
            ParseMode::Object => {
                pointer.fetch_add(1, Ordering::SeqCst);
                Self::parse_skip_whitespace(json, pointer);
                let mut object = vec![];
                while let Some(c) = json.get(pointer.load(Ordering::SeqCst)) {
                    match *c {
                        '"' => {
                            pointer.fetch_add(1, Ordering::SeqCst);
                            let mut key = String::new();
                            while let Some(c) = json.get(pointer.load(Ordering::SeqCst)) {
                                if *c == '"' {
                                    pointer.fetch_add(1, Ordering::SeqCst);
                                    break;
                                }
                                key.push(*c);
                                pointer.fetch_add(1, Ordering::SeqCst);
                            }
                            // println!("key: {:?}", key);
                            Self::parse_skip_whitespace(json, pointer);
                            if let Some(c) = json.get(pointer.load(Ordering::SeqCst)) {
                                if *c == ':' {
                                    pointer.fetch_add(1, Ordering::SeqCst);
                                    Self::parse_skip_whitespace(json, pointer);
                                    object.push((key, match *json.get(pointer.load(Ordering::SeqCst)).unwrap() {
                                        '[' => Self::from_json_intern(json, pointer, ParseMode::Array),
                                        '{' => Self::from_json_intern(json, pointer, ParseMode::Object),
                                        '"' => Self::from_json_intern(json, pointer, ParseMode::String),
                                        _ => panic!("Invalid character in object: {}: {}", c, pointer.load(Ordering::SeqCst)),
                                    }));
                                } else {
                                    panic!("Invalid character in object: {}: {}", c, pointer.load(Ordering::SeqCst));
                                }
                            } else {
                                panic!("Unexpected end of input in object");
                            }
                        }
                        '}' => {
                            pointer.fetch_add(1, Ordering::SeqCst);
                            break;
                        }
                        _ => panic!("Invalid character in object: {}: {}", c, pointer.load(Ordering::SeqCst)),
                    }
                    Self::parse_skip_whitespace(json, pointer);
                    if let Some(c) = json.get(pointer.load(Ordering::SeqCst)) {
                        match *c {
                            ',' => {
                                pointer.fetch_add(1, Ordering::SeqCst);
                                Self::parse_skip_whitespace(json, pointer);
                            }
                            '}' => {
                                pointer.fetch_add(1, Ordering::SeqCst);
                                break;
                            }
                            _ => panic!("Invalid character in object: {}: {}", c, pointer.load(Ordering::SeqCst)),
                        }
                    } else {
                        panic!("Unexpected end of input in object");
                    }
                }
                Data::Object(object)
            },
            ParseMode::String => {
                pointer.fetch_add(1, Ordering::SeqCst);
                let mut string = String::new();
                while let Some(c) = json.get(pointer.load(Ordering::SeqCst)) {
                    if *c == '"' {
                        pointer.fetch_add(1, Ordering::SeqCst);
                        break;
                    }
                    string.push(*c);
                    pointer.fetch_add(1, Ordering::SeqCst);
                }
                Data::String(string)
            }
        }
    }
    fn from_json(json: String) -> Data {
        let mut pointer = AtomicUsize::new(0);
        let json_chars: Vec<char> = json.chars().collect();
        Self::from_json_intern(&json_chars, &mut pointer, ParseMode::Object)
    }
}


fn count_province(data: &Data) -> usize {
    if let Data::Object(object) = data {
        let mut cities_in_provinces: Vec<BTreeSet<String>> = vec![];
        for (key, value) in object {
            let mut cities = BTreeSet::new();
            cities.insert(key.clone());
            if let Data::Array(array) = value {
                array
            } else {
                panic!("Invalid value: {:?}", value);
            }.iter().for_each(|x| {
                if let Data::String(s) = x {
                    cities.insert(s.clone());
                } else {
                    panic!("Invalid city: {:?}", x);
                }
            });
            match cities_in_provinces.iter_mut().find(|x| {
                !x.is_disjoint(&cities)
            }) {
                Some(x) => {
                    x.extend(cities);
                }
                None => {
                    cities_in_provinces.push(cities);
                }
            }
        }
        // println!("cities_in_provinces: {:?}", cities_in_provinces);
        cities_in_provinces.len()
    } else {
        0
    }
}

pub fn count_provinces() -> String {
    let json_str = include_str!("../district.json");
    let data = Data::from_json(json_str.to_string());
    if let Data::Object(object) = data {
        let values: Vec<_> = object.iter().map(|(_, value)| count_province(value).to_string()).collect();
        // String join as 1,2,3
        values.join(",")
    } else {
        "".to_string()
    }
}
